package Plants;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import SmartGrid.SmartGrid;

public class GraphAlgorithms {

	public static Map<PlantPair, Float> shortestDistances;
	public static Map<PlantPair, PowerPlant> next;
	
	/**
	 * Public wrapper function to get the shortest distance from i to j
	 * @param i
	 * @param j
	 * @return
	 */
	public static float getShortestDistance(PowerPlant i, PowerPlant j)
	{
		PlantPair pair = new PlantPair(i,j);
		return shortestDistances.get(pair);
	}
	
	/**
	 * http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
	 * 12 procedure FloydWarshall ()
	 * 13    for k := 1 to n
	 * 14       for i := 1 to n
	 * 15          for j := 1 to n
	 * 16             path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );
	 */
	public static void FloydWarshall()
	{
		if(shortestDistances != null) return;
		shortestDistances = new HashMap<PlantPair, Float>();
		next = new HashMap<PlantPair, PowerPlant>();
		Iterator<PowerPlant> iter = SmartGrid.allPlants.values().iterator();
		while(iter.hasNext())
		{
			PowerPlant plant_i = iter.next();
			Iterator<PowerPlant> iter2 = SmartGrid.allPlants.values().iterator();
			while(iter2.hasNext())
			{
				PowerPlant plant_j = iter2.next();
				float distance = 0;
				if(plant_i.equals(plant_j))
				{
					distance = 0;
				}
				else
				{
					PowerLine line = plant_i.getLineWith(plant_j);
					if(line == null)
						distance = Float.POSITIVE_INFINITY;
					else
						distance = line.getDistance();
				}
				try
				{
					shortestDistances.put(new PlantPair(plant_i, plant_j), distance);
					shortestDistances.put(new PlantPair(plant_j, plant_i), distance);
				}
				catch(Exception e)
				{
					e.printStackTrace();
				}
			}
		}
		
		iter = SmartGrid.allPlants.values().iterator();
		while(iter.hasNext())
		{
			PowerPlant plant_k = iter.next();
			Iterator<PowerPlant >iter2 = SmartGrid.allPlants.values().iterator();
			while(iter2.hasNext())
			{
				PowerPlant plant_i = iter2.next();
				Iterator<PowerPlant> iter3 = SmartGrid.allPlants.values().iterator();
				while(iter3.hasNext())
				{
					PowerPlant plant_j = iter3.next();
					PlantPair ij = new PlantPair(plant_i, plant_j);
					PlantPair ik = new PlantPair(plant_i, plant_k);
					PlantPair kj = new PlantPair(plant_k, plant_j);
					if(shortestDistances.get(ij) > shortestDistances.get(ik) + shortestDistances.get(kj))
					{
						shortestDistances.put(ij, shortestDistances.get(ik) + shortestDistances.get(kj));
						next.put(ij, plant_k);
					}
				}
			}
		}
	}
	
	/**
	 * Public wrapper function for shortest path reconstruction.  Under the hood algorithm is found
	 * in method getPath
	 * @param i
	 * @param j
	 * @return
	 */
	public static List<PowerPlant> GetPath(PowerPlant i, PowerPlant j)
	{
		String path = getPath(i,j);
		String[] nodes = path.split(" ");
		List<PowerPlant> plants = new ArrayList<PowerPlant>();
		for(int k = 0; k < nodes.length; k++)
		{
			String plantname = nodes[k];
			PowerPlant p = SmartGrid.allPlants.get(plantname);
			plants.add(p);
		}
		return plants;
	}
	
	/**
	 *  9 procedure GetPath (i,j)
	 *  10    if path[i][j] equals infinity then
	 *  11      return "no path";
	 *  12    int intermediate := next[i][j];
	 *  13    if intermediate equals 'null' then
	 *  14      return " ";   there is an edge from i to j, with no vertices between
	 *  15    else
	 *  16      return GetPath(i,intermediate) + intermediate + GetPath(intermediate,j);
	 * @param i
	 * @param j
	 */
	private static String getPath(PowerPlant i, PowerPlant j)
	{
		PlantPair ij = new PlantPair(i, j);
		if(shortestDistances.get(ij) == Float.POSITIVE_INFINITY)
			return "No path.";
		PowerPlant intermediate = next.get(ij);
		if(intermediate == null)
			return " ";
		else
			return getPath(i, intermediate) + intermediate + getPath(intermediate, j);
	}
	
}
